/*
 *  POJ3126: Prime Path
 */

/*-------- Includes --------*/
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

/*-------- Types --------*/
struct Para {
    int v;  // value
    int d;  // depth
public:
    Para() {}
    Para(int vv, int dd) : v(vv), d(dd) {}
};

/*-------- Global Variables --------*/
const int prim[25] = {
     2,  3,  5,  7, 11,
    13, 17, 19, 23, 29,
    31, 37, 41, 43, 47,
    53, 59, 61, 67, 71,
    73, 79, 83, 89, 97
};  // prime table from 2 to 99

bool isUsed[9000];  // mark array

/*-------- Function Prototypes --------*/
bool isPrime(int n);

/*-------- Main Function --------*/
int main(int argc, char const *argv[])
{
    int nCase;
    int src;
    int dst;

    cin >> nCase;

    while (nCase--) {
        cin >> src >> dst;

        queue<Para> que;
        Para        par;

        // initialize
        memset(isUsed, false, sizeof(isUsed));

        // first element
        que.push(Para(src, 0));
        isUsed[src - 1000] = true;  // mark

        while (!que.empty()) {
            par = que.front(); que.pop();

            // base case: find the solution
            if (par.v == dst) break;

            // four digits
            int v = par.v;
            int bit[4];

            bit[0] = v % 10;
            for (int i = 1; i < 4; i++) {
                v /= 10; bit[i] = v % 10;
            }

            // the most significant bit
            for (int i = 1; i < 10; i++) {
                // cut off
                if (i == bit[3]) continue;

                v = par.v + (i - bit[3]) * 1000;

                // cut off
                if (isUsed[v - 1000] || !isPrime(v)) continue;

                que.push(Para(v, par.d + 1));
                isUsed[v - 1000] = true;    // mark
            }

            // 0 to 2 bit
            for (int i = 0; i < 3; i++) {
                int times = 1;
                for (int j = 0; j < i; j++) times *= 10;

                for (int j = 0; j < 10; j++) {
                    // cut off
                    if (j == bit[i]) continue;

                    v = par.v + (j - bit[i]) * times;

                    // cut off
                    if (isUsed[v - 1000] || !isPrime(v)) continue;

                    que.push(Para(v, par.d + 1));
                    isUsed[v - 1000] = true;    // mark
                }
            }
        }

        // print result
        if (par.v == dst) cout << par.d << endl;
        else              cout << "Impossible" << endl;
    }

    return 0;
}

/*-------- Functions --------*/
bool isPrime(int n)
{
    // isPrime for four digits number
    for (int i = 0; i < 25; i++)
        if (n % prim[i] == 0) return false;

    return true;
}
